嘿！各位工程師朋友們，今天我們來聊聊一個相當經典的 Leetcode 題目，叫做「Longest Substring Without Repeating Characters」，也就是尋找字串中最長不重複的子字串。這題不僅是面試中的常客，還能訓練我們對字串與滑動窗口（sliding window）的掌握程度。準備好了嗎？讓我們輕鬆解鎖這題吧！

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest 

substring

 without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

中文描述

給定一個字串 s，你需要找出其中最長的不重複字元子字串，並回傳其長度。

範例：

• 範例 1:

  • 輸入: s = "abcabcbb"
  • 輸出: 3
  • 解釋: 最長的子字串為 "abc"，長度為 3。

• 範例 2:

  • 輸入: s = "bbbbb"
  • 輸出: 1
  • 解釋: 最長的子字串為 "b"，長度為 1。

• 範例 3:

  • 輸入: s = "pwwkew"
  • 輸出: 3
  • 解釋: 最長的子字串為 "wke"，長度為 3。
  • 注意答案必須是連續的子字串，因此 "pwke" 是子序列，並非子字串。

實作

讓我們直接進入 TypeScript 的實作吧！我們將採用滑動窗口的技術來解這題，這個方法能讓我們一次遍歷字串，同時動態地調整我們的窗口來取得最長不重複子字串。

function lengthOfLongestSubstring(s: string): number {
    const seenChars = new Map(); // 用來記錄已經遇到的字符位置
    let maxLength = 0; // 紀錄最長不重複子字串的長度
    let left = 0; // 窗口的左邊界

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];

        // 如果當前字元在Map裡，且位置大於等於左邊界，更新左邊界
        if (seenChars.has(currentChar) && seenChars.get(currentChar) >= left) {
            left = seenChars.get(currentChar) + 1;
        }

        // 將當前字元的位置更新到Map
        seenChars.set(currentChar, right);

        // 計算當前窗口的長度
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

解釋

這個解法採用了滑動窗口（Sliding Window）的技巧，搭配一個 Map 來記錄每個字元最後出現的位置。讓我們來一步步解釋：

1. Map 記錄字元位置：我們使用 Map 來儲存每個字元最後一次出現的位置，這樣當我們遇到一個重複的字元時，便可以將窗口的左邊界移動到重複字元的下一個位置，確保子字串中的字元都是不重複的。

2. 動態調整窗口大小：窗口的左邊界 left 會在遇到重複字元時向右移動，而右邊界 right 則會隨著遍歷字串逐步擴大。

3. 更新最長子字串長度：在每次更新窗口時，我們都會計算當前不重複字串的長度，並更新 maxLength。

這樣一來，我們就能以 O(n) 的時間複雜度完成這道題目。看似簡單，但這背後隱藏著一些經典的編程技巧！

解題脈絡：

這道題一開始看似很直觀，只要找出所有的子字串並判斷是否有重複字元就好，但當你想到「如何有效率地判斷並動態調整範圍」時，就會意識到滑動窗口的威力。滑動窗口的思想就是：當我們發現子字串中有重複字元時，立即縮小左邊界，這樣才能確保窗口內的子字串符合題目要求。

本次要點：

1. 滑動窗口技巧：在解這類字串處理問題時，滑動窗口能顯著提高效率。
2. Map 用法：使用 Map 記錄字元位置，是快速更新與查詢的好方法。
3. 實際應用場景：這道題目不僅能夠應用於字串處理問題，還可以幫助我們理解一些動態範圍處理的概念，適合在實際項目中解決類似需求。

希望大家從這次的題目中學到滑動窗口的精髓，下次遇到類似的題目時，可以更快地找到解法！